#include <bits/stdc++.h>
using namespace std;

/*
2179. 统计数组中好三元组数目
已解答
困难
相关标签
相关企业
提示
给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。

好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。

请你返回好三元组的 总数目 。

 

示例 1：

输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3]
输出：1
解释：
总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。
这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 1 个好三元组。
示例 2：

输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
输出：4
解释：总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。
 

提示：

n == nums1.length == nums2.length
3 <= n <= 105
0 <= nums1[i], nums2[i] <= n - 1
nums1 和 nums2 是 [0, 1, ..., n - 1] 的排列。
*/

// 法一
// 树状数组类（支持快速前缀和查询与单点更新）
class BIT {
	private:
	vector<int> tree;  // 树状数组存储
	int n;             // 数组最大容量
public:
	// 构造函数：初始化大小为size的树状数组（实际存储空间+2以避免边界处理）
	BIT(int size) : n(size), tree(size + 2, 0) {}
	
	// 单点更新：在位置x处增加1（用于计数）
	void update(int x) {
		// 按树状数组规则向上更新所有相关节点（x & -x 获取最低有效位）
		for (; x <= n; x += x & -x)
			tree[x]++;
	}
	
	// 前缀和查询：获取[1, x]区间的元素计数
	int query(int x) {
		int res = 0;
		// 按树状数组规则向下累加所有相关节点
		for (; x > 0; x -= x & -x)
			res += tree[x];
		return res;
	}
};
	
class Solution {
	public:
	long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
		int n = nums1.size();
		// 步骤1：建立nums2的值到索引的映射（O(1)快速查找）
		unordered_map<int, int> pos;
		for (int i = 0; i < n; ++i)
			pos[nums2[i]] = i;
		
		// 步骤2：将nums1转换为nums2中的位置数组，并调整下标从1开始（适配树状数组）
		vector<int> arr(n);
		for (int i = 0; i < n; ++i)
			arr[i] = pos[nums1[i]] + 1;  // +1避免树状数组的0下标问题[8](@ref)

		// 步骤3：正向扫描计算每个元素左侧比它小的元素数量
		BIT bit1(n + 1);          // 树状数组用于动态维护元素计数
		vector<int> left(n);      // left[i]表示arr[0..i-1]中<arr[i]的元素数量
		for (int i = 0; i < n; ++i) {
			left[i] = bit1.query(arr[i] - 1); // 查询当前元素左侧的较小元素数量[6,7](@ref)
			bit1.update(arr[i]);  // 将当前元素加入树状数组
		}

		// 步骤4：逆向扫描计算每个元素右侧比它大的元素数量
		BIT bit2(n + 1);
		vector<int> right(n);     // right[i]表示arr[i+1..n-1]中>arr[i]的元素数量
		for (int i = n - 1; i >= 0; --i) {
			// 总剩余元素数(n-1-i) - 已处理的较小元素数 = 右侧较大元素数
			right[i] = (n - 1 - i) - bit2.query(arr[i]);
			bit2.update(arr[i]);  // 逆向维护树状数组
		}

		// 步骤5：累加每个元素作为中间元素的三元组数量（组合数乘法原理）
		long long ans = 0;
		for (int i = 0; i < n; ++i)
			ans += 1LL * left[i] * right[i];  // left[i]*right[i]为以i为中心的三元组数[6](@ref)
		
		return ans;
	}
};

// 法二
// 树状数组（Fenwick Tree）实现，用于高效维护前缀和及单点更新
class FenwickTree {
	private:
	vector<int> tree; // 树状数组存储
public:
	// 构造函数，初始化大小为size的树状数组，所有元素初始为0
	FenwickTree(int size) : tree(size + 1, 0) {}

	// 更新操作：在index位置增加delta（内部转为1-based处理）
	void update(int index, int delta) {
		index++; // 转为1-based索引
		while (index < tree.size()) {
			tree[index] += delta;
			index += index & -index; // 移动到父节点
		}
	}

	// 查询操作：返回前index个元素的前缀和（0-based）
	int query(int index) {
		index++; // 转为1-based索引
		int res = 0;
		while (index > 0) {
			res += tree[index];
			index -= index & -index; // 移动到前一节点
		}
		return res;
	}
};

class Solution {
public:
	long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
		int n = nums1.size();
		vector<int> pos2(n); // 记录nums2中每个元素的索引位置
		for (int i = 0; i < n; i++) {
			pos2[nums2[i]] = i; // 元素值nums2[i]的索引位置是i
		}

		// reversedIndexMapping[k]表示：nums2中位置k对应的元素，其在nums1中的索引位置
		vector<int> reversedIndexMapping(n);
		for (int i = 0; i < n; i++) {
			int pos_in_nums2 = pos2[nums1[i]]; // nums1[i]在nums2中的位置
			reversedIndexMapping[pos_in_nums2] = i; // 将nums2的位置映射回nums1的索引
		}

		FenwickTree tree(n); // 树状数组维护已处理的元素分布
		long long res = 0;

		// 按nums2的顺序遍历元素，计算其在nums1中对应的位置pos
		for (int value = 0; value < n; value++) {
			int pos = reversedIndexMapping[value]; // 当前元素在nums1中的索引
			
			// 查询已处理元素中比pos小的元素个数（即左侧可用元素数）
			int left = tree.query(pos - 1);
			tree.update(pos, 1); // 将当前pos插入树状数组
			
			// 计算右侧比pos大的元素数：
			// 总共有 (n-1 - pos) 个元素比pos大，减去已处理的比pos大的元素数 (value - left)
			int right = (n - 1 - pos) - (value - left);
			
			// 累加以当前元素为中心的三元组数量
			res += (long long)left * right;
		}

		return res;
	}
};